import collections


class Solution(object):
    def beforeAndAfterPuzzles(self, phrases):
        """
        :type phrases: List[str]
        :rtype: List[str]
        """
        out = set()
        c = collections.Counter(phrases)
        first_d = collections.defaultdict(set)
        last_d = collections.defaultdict(set)
        for words in phrases:
            word_list = words.split(' ')
            first_d[word_list[0]].add(words)
            last_d[word_list[-1]].add(words)
        for l_w in last_d:
            if l_w in first_d:
                for w1 in last_d[l_w]:
                    for w2 in first_d[l_w]:
                        if w1 != w2 or (w1 == w2 and c[w1] >= 2):
                            pre = w1.split(' ')[:-1]
                            suff = w2.split(' ')[1:]
                            word = pre + [l_w] + suff
                            out.add(' '.join(word))
        out = list(out)
        out.sort()
        return out


data = Solution()
phrases = ["writing code", "code rocks"]
print(data.beforeAndAfterPuzzles(phrases))
phrases = ["mission statement", "a quick bite to eat", "a chip off the old block", "chocolate bar",
           "mission impossible",
           "a man on a mission", "block party", "eat my words", "bar of soap"]
print(data.beforeAndAfterPuzzles(phrases))
phrases = ["a", "b", 'b', "a"]
print(data.beforeAndAfterPuzzles(phrases))
